/* 3.4 Минимальное остовное дерево (Алгоритм Крускала) */

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

#define M INT_MAX

struct edge
{
	int x, y, w;
};

int cmp(const void* v1, const void* v2);

int main()
{
        int n = 6;
        int a[10][10] = {{M, 3, 8, 2, M, 7},
                         {3, M, M, M, M, M},
                         {8, M, M, 1, 4, M},
                         {2, M, 1, M, 2, 1},
                         {M, M, 4, 2, M, 5},
                         {7, M, M, 1, 5, M}};
	/*int a[10][10] ={{M, 3, M, M, 6, 5},
			{3, M, 1, M, M, 4},
			{M, 1, M, 6, M, 4},
			{M, M, 6, M, 8, 5},
			{6, M, M, 8, M, 2},
			{5, 4, 4, 5, 2, M}};*/

	int i = 0, j = 0, k = 0;
	int c[10] = {0};
	struct edge e[55] = {0};
	for (i = 0; i < n; i++)	c[i] = i;
	for (i = 0; i < n; i++) 
		for (j = i+1; j < n; j++)
			if (a[i][j] != M) 
			{
				e[k].x = i;
				e[k].y = j;
				e[k].w = a[i][j];
				k++;
			}
	qsort(e, k, sizeof(struct edge), cmp);
	/*for (i = 0; i < k; i++)
		printf("%d %d %d\n",e[i].x, e[i].y, e[i].w);*/
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			a[i][j] = M;
	for (i = 0; i < k; i++)
	{
		//int early_exit = 1;
		if (c[e[i].x] != c[e[i].y]) 
		{
			int x = e[i].x;
			int y = e[i].y;
			int r = c[y];
			a[x][y] = e[i].w;
			a[y][x] = e[i].w;
			for (j = 0; j < n; j++) 
				if (c[j] == r) c[j] = c[x];	
			//early_exit = 0;
		}
		//if (early_exit) break;
	}			
	
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			if (a[i][j] == M) printf("M ");
			else printf("%d ", a[i][j]);
		printf("\n");
	}

	return 0;
}

int cmp(const void* v1, const void* v2)
{
	struct edge *e1 = (struct edge*) v1;
	struct edge *e2 = (struct edge*) v2;
	return e1->w - e2->w;
}
